Computer systems typically comprise a combination of computer programs and hardware, such as semiconductors, transistors, chips, circuit boards, storage devices, and processors. The computer programs are stored in the storage devices and are executed by the processors. Fundamentally, computer systems are used for the storage, manipulation, and analysis of data. One mechanism for managing data is called a database management system (DBMS), which may also be called a database system or simply a database.
A relational database (RDB) organizes data in tables that have rows, which represent individual entries, tuples, or records in the database, and columns, fields, or attributes, which define what is stored in each row, entry, tuple, or record. Each table has a unique name within the database and each column has a unique name within the particular table. The database also has one or more indexes, which is a data structure that informs the DBMS of the location of a certain record in a table given an indexed column value, analogous to a book index informing the reader on which page a given word appears. The database accesses the data in a record via a key. A key specifies the name of a column and a data value that exists in one of the records in that column.
The most common way to retrieve data from a database is through queries, which may originate from user interfaces, application programs, or remote computer systems, such as clients. A query is an expression evaluated by the DBMS, in order to retrieve data from the database that satisfies or meets the criteria or conditions specified in the query. Although the query requires the return of a particular data set in response, the method of query execution is typically not specified by the query. Thus, after the DBMS receives a query, the DBMS interprets the query and determines what internal steps are necessary to satisfy the query. These internal steps may comprise an identification of the table or tables specified in the query, the record or records selected in the query, and other information such as whether to use an existing index, whether to build a temporary index, whether to scan a table instead of randomly accessing the table via an index, whether to use a temporary file to execute a sort, and/or the order in which the tables are to be joined together to satisfy the query.
When taken together, these internal steps are referred to as an execution plan or a query plan. The DBMS often saves the execution plan for later use. Then, when the user or program object repeats the same query, the DBMS finds, reuses, and re-executes the saved execution plan instead of undergoing the time-consuming process of recreation.
Many different execution plans may be created for any one query, each of which would return the same data set that satisfies the query, yet the different execution plans may provide widely different performance. Hence, the query optimizer often creates multiple prospective execution plans and then chooses the best, fastest, or least expensive one to execute.